An exposure apparatus is used in a lithograph step of the process for manufacturing a semiconductor device. The lithograph step is a step in which a circuit pattern of a semiconductor device is transferred onto a substrate (silicon substrate, glass substrate, wafer, or the like). The exposure apparatus illuminates a mask (reticle) with an illumination optical system by use of light from a light source, and thereby transfers the circuit pattern formed on the mask through a projection optical system or the like onto the wafer. In recent years, due to the developments in pattern miniaturization for a semiconductor device, the wafer is exposed on a plurality of occasions by use of a plurality of masks to thereby execute a plurality of exposure operations to form a corresponding plurality of mask patterns on a single layer on the wafer. Generally, the resolution limit of the exposure apparatus is expressed by hp=k1×λ/NA. The denotation hp is an abbreviation for half pitch, and is half the shortest distance between adjacent patterns. The denotation k1 is the process factor, λ is the exposure light wavelength, and NA is the numerical aperture of the exposure apparatus. The plurality of exposure operations is a technique of dividing and exposing the pattern, that has a smaller half pitch than the half pitch of the resolution limit of the exposure apparatus, into a plurality of mask patterns to thereby enable the resolution of a more detailed pattern than the resolution limit that does not impart a sufficient exposure margin with a single conventional exposure.
The method of dividing a single layout (pattern) into a plurality of mask patterns includes a characteristic such as divided coating of color which is generally termed a coloring problem. The feature of pattern division may use an expression such as divided color coating. A method of dividing an original target pattern into a plurality of mask patterns includes the method disclosed in Patent Literature 1 that applies a division rule by use of an iterative method. More specifically, this method determines a division rule, and attributes a mask as a first mask or attributes a mask as a second mask by application of the division rule to the pattern under consideration, and then repeats that operation for each pattern. Furthermore, Patent Literature 2 discloses a pattern division method using a conflict graph and a method of mathematical programming. A conflict graph is a graph that is configured from points and sides, and in the example of pattern division, each mask pattern is expressed by points, and patterns that exceed the resolution limit are connected by a side. Pattern division is calculated using a method of mathematical programming so that the mask number of both sides is a different number.